package biolabs.model.abscretion;

import java.util.Iterator;

import biolabs.util.Graph;
import biolabs.util.Graph.Edge;
import biolabs.util.Graph.Vertex;

/**
 * Algorithm for substance redistribution.
 *
 * @author Tomas Mikula
 */
public class SubstanceRedistribution {

	public static class EdgeData {
		private int flow;
		public EdgeData(){
			flow = 0;
		}
	}

	public static void redistribute(Graph<AbscretionPoint, EdgeData> graph) {
		int nt = 0; // number of targets

		// Compute the balance of each vertex.
		// During the algorithm, amount will be used to store balance.
		for(AbscretionPoint v: graph.vertexValues()) {
			v.amount -= v.demand;
			if(v.amount < 0)
				++nt;
			v.active = v.amount != 0;
		}

		while(nt>0) {
			int maxflow = Integer.MAX_VALUE;

			// go through sources and compute how much they can provide to each edge
			for(Vertex<AbscretionPoint, EdgeData> vv: graph.vertices()) {
				AbscretionPoint v = vv.getData();
				if(!v.active) { /* do nothing */ }
				else if(v.amount > 0) {
					// count the number of neighbor targets
					int n=0;
					for(AbscretionPoint w: vv.neighborData())
						if(w.amount < 0)
							++n;
					if(n==0) { // no neighbor targets => we are finished with this vertex
						v.active = false;
						continue;
					}

					int f = v.amount / n;
					int g = v.amount % n;
					int flow = (g>0) ? (f+1) : f;
					if(flow < maxflow)
						maxflow = flow;

					// offer f+1 to first g neighbor targets and f to the remaining
					Iterator<Edge<AbscretionPoint, EdgeData>> eit = vv.incidentEdges().iterator();
					while(g>0) {
						Edge<AbscretionPoint, EdgeData> e = eit.next();
						if(e.getOppositeEndOf(v).amount < 0){
							e.getData().flow = f+1;
							--g;
						}
					}
					while(eit.hasNext()) {
						Edge<AbscretionPoint, EdgeData> e = eit.next();
						if(e.getOppositeEndOf(v).amount < 0)
							e.getData().flow = f;
					}
				} else if(v.amount == 0) {
					v.active = false;
				}
			}

			// go through targets and check how much of the offers they can accept
			for(Vertex<AbscretionPoint, EdgeData> vv: graph.vertices()) {
				AbscretionPoint v = vv.getData();
				if(v.active && v.amount < 0) {
					// count the number of neighbor sources
					int n = 0;
					for(AbscretionPoint w: vv.neighborData())
						if(w.amount > 0)
							++n;
					if(n==0) { // no neighbor sources => we are finished with this vertex
						v.active = false;
						--nt;
						continue;
					}

					int newbalance = v.amount + n*maxflow;
					if(newbalance > 0) {
						maxflow -= newbalance/n;
						newbalance = v.amount + n*maxflow;
						assert newbalance >= 0;
						assert newbalance < n;
					}
				}
			}

			// transfer maxflow (or maxflow-1) by each source->target edge
			for(Vertex<AbscretionPoint, EdgeData> vv: graph.vertices()) {
				AbscretionPoint v = vv.getData();
				if(v.active && v.amount < 0) {
					// count the number of neighbor sources
					int n = 0;
					for(AbscretionPoint w: vv.neighborData())
						if(w.amount > 0)
							++n;
					if(n==0) { // no neighbor sources => we are finished with this vertex
						v.active = false;
						--nt;
						continue;
					}

					 // at most how many edges can transfer maxflow
					int nmaxflow = n - (v.amount + n*maxflow);

					for(Edge<AbscretionPoint, EdgeData> edge: vv.incidentEdges()) {
						EdgeData e = edge.getData();
						AbscretionPoint w = edge.getOppositeEndOf(v);
						if(w.amount > 0) {
							int flow = (maxflow < e.flow) ? maxflow : e.flow;
							if(flow == maxflow) {
								if(nmaxflow > 0)
									--nmaxflow;
								else
									--flow;
							}
							w.amount -= flow;
							v.amount += flow;
						}
					}
					assert(v.amount <= 0);
					if(v.amount == 0)
						--nt;
				}
			}
		}

		// turn balance back to amount by adding demand
		for(AbscretionPoint v: graph.vertexValues()) {
			v.amount += v.demand;
		}

	}
}
